/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-07-15
 * Time: 16:41
 */
public class HanoiTower {
    // 统计移动次数
    private static int count = 0;

    /**
     * 汉诺塔递归函数
     * @param n 圆盘数量
     * @param from 起始柱
     * @param helper 辅助柱
     * @param to 目标柱
     */
    public static void hanoi(int n, char from, char helper, char to) {
        // 基础情况：n=1时直接移动
        if (n == 1) {
            count++;
            System.out.println("第" + count + "步：将圆盘" + n + "从" + from + "移到" + to);
            return;
        }
        // 递归：n-1个圆盘从from→helper（借助to）
        hanoi(n - 1, from, to, helper);
        // 移动第n个圆盘从from→to
        count++;
        System.out.println("第" + count + "步：将圆盘" + n + "从" + from + "移到" + to);//一个圆盘已经不需要再拆开了，所以不需要使用递归
        // 递归：n-1个圆盘从helper→to（借助from）
        hanoi(n - 1, helper, from, to);
    }

    public static void main(String[] args) {
        int n = 3; // 圆盘数量
        System.out.println("汉诺塔移动步骤（" + n + "个圆盘）：");
        hanoi(n, 'A', 'B', 'C');
        System.out.println("总移动次数：" + count); // n个圆盘的总次数为2ⁿ - 1
    }
}